public class Test18 {
    public static boolean hasSubtree(TreeNode root1,TreeNode root2){
        if(root1 == root2) return true;
        if(root2 == null) return true;
        if(root1 == null) return false;
        boolean res = false;
        if(root1.val == root2.val) res = mach(root1,root2);
        if(res) return true;
        return hasSubtree(root1.left,root2) || hasSubtree(root1.right,root2);
    }
    public static boolean mach(TreeNode root1,TreeNode root2){
        if(root1 == root2) return true;
        if(root2 == null) return true;
        if(root1 == null) return false;

        if(root1.val == root2.val) return mach(root1.left,root2.left) && mach(root1.right,root2.right);

        return false;
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode();
        root1.val = 8;
        root1.right = new TreeNode();
        root1.right.val = 7;
        root1.left = new TreeNode();
        root1.left.val = 8;
        root1.left.left = new TreeNode();
        root1.left.left.val = 9;
        root1.left.right = new TreeNode();
        root1.left.right.val = 2;
        root1.left.right.left = new TreeNode();
        root1.left.right.left.left = new TreeNode();
        root1.left.right.left.left.val = 3;
        root1.left.right.left.right = new TreeNode();
        root1.left.right.left.right.val = 8;

        TreeNode root2 = new TreeNode();
        root2.val = 8;
        root2.left = new TreeNode();
        root2.left.val = 9;
        root2.right = new TreeNode();
        root2.right.val = 2;

        System.out.println(hasSubtree(root1, root2));
        System.out.println(hasSubtree(root2, root1));
        System.out.println(hasSubtree(root1, root1.left));
        System.out.println(hasSubtree(root1, null));

    }
}
